\chapter{Стандартная библиотека}

\section{Лекция 28.02.2012. Последовательные контейнеры}

\subsection{vector<bool>}

Для bool существует специализация шаблона vector, и это понятно, так как хранить вектор bool-ов можно гораздо эффективнее по памяти, но это влечет некоторые
проблемы, например:

\begin{lstlisting}
vector<bool> v;
...
bool *p = &v[i];
v[k] = true;
...
\end{lstlisting}

Без дополнительных сущностей такие проблемы решить не получится, для устранения этой неприятности можно воспользоваться proxy-объектом:
\begin{lstlisting}
...
proxy_obj operator[](...)
...
\end{lstlisting}

как должен быть устроен proxy\_obj? Как минимум он хранит индекс нужного bool-а и указатель на vector, в котором он хранится:
\begin{lstlisting}
class proxy_obj {
int index;
vector<bool> *ptr;
...
operator bool();
proxy_obj& operator=(bool);
...
};
\end{lstlisting}

Класс proxy\_obj может быть объявлент приватной внутренней структурой специализации vector на bool, дело в том, что приватность (права доступа) действует только
на уровне имени, т. е. при следующем объявлении:
\begin{lstlisting}
template <>
class vector<bool> {
private:
	struct proxy_obj {
		...
	};
...
};
\end{lstlisting}
мы не сможем создавать объектыg proxy\_obj снаружи, но при этом, когда объект создан, мы можем обращаться к его методам.

\section{Ассоциативные контейнеры}

\subsection{Галопом по ассоциативным контейнерам}

Существует 4 ассоциативных контейнера:
\begin{itemize}
\item set и multiset, объявленные в заголовке <set>. Эти классы являются реализацией упорядоченного множества на базе дерева, типичный пример использования такой:
\begin{lstlisting}
set<int> s;
s.insert(5);
s.insert(4);
s.insert(7);
for (set<int>::iterator i = s.begin(); i != s.end(); ++i)
	cout << *i << '\n'
\end{lstlisting}
Так как по сути используется некоторое сбалансированное дерево, то большинство операций работают за O(log n) (поиск, вставка и тд). Кстати функция поиска возвращает
итератор, и если элемент не найден, то возвращается end итератор:
\begin{lstlisting}
it = s.find(5);
if (it != s.end()) {
...
}
\end{lstlisting}
Метод insert класса set возвращает пару итератор и булеове значение, последнее показывает был ли элемент вставлен или нет, дело в том, что если элемент присутсвует
в set, то он не перезаписывается при повторной вставке, и если вам это нужно сделать, придется делать это явно.

Отличие multiset от set следует из названия, multiset допускает повторения, а функция find возвращает первый найденный элемент дерева (при этом, это не
значит, что найденный элемент был добавлен первым).

И еще одно важное замечание, в set нельзя менять значения через итераторы, что понятно, так как значение влияет на положение в дереве и нужно как-то отслеживать
изменение в этом случае.

\item map и multimap, объявленные в заголовке <map>. Назначение этих объектов вполне очевидно - этот контейнер хранит упорядоченные пары объектов (ключ и значение).
map как и set построен на сбалансированных деревьях поиска, типчное использование выглядит примерно так:
\begin{lstlisting}
map<string, int> m;
m.insert(std::pair<string, int>("Vasja", 12345));
...
m.insert(map<string, int>::value_type("Vasja", 12346));
...
m.insert(std::make_pair("Vasja", 12347));
...
\end{lstlisting}
Последний вариант вставки короче да и выглядит приятнее, в последнем случае используется шаблонная функция, которая выводит свои параметры, и естественно,
иногда она может вывести не те типы, наличие в pair шаблонного конструктора преобразования от pair с другими параметрами исправляет положение.
Есть и альтернативные методы добавления. insert работает аналогично insert в set, но здесь это уже важнее чем в set, так как для map обновление гораздо
более осмысленная операция.

Попсовый метод добавления с обновлением значения выглядит следующим образом:
\begin{lstlisting}
m["Vasja"] = 12345;
\end{lstlisting}
этот метод работает только, если у типа значения есть конструктор по умолчанию, в отличие от предыдущих методов, кроме того может создаться ошибочное впечатление,
что оператор индекса работает за константну, но на самом деле за ним стоит опять же логарифм. Ну и наконец, оператор индексирования не работает с multimap и
константными map, так как если индекс не найден, он будет добавлен, что невозможно для константного объекта.

Так в map хранится не один элемент, а пара, то вывод элементов map немного менятеся:
\begin{lstlisting}
for (map<string, int>::iterator i = m.begin(); i != m.end(); ++i)
	cout << i->first << " " << i->second << "\n";
\end{lstlisting}

Также отметим, что в паре первое значение является константой, поэтому его менять по итератору нельзя, в то время как второе значение можно менять.
\end{itemize}

\subsection{Общие методы}

\begin{itemize}
\item find - возвращает итератор на искомый объект (или на первый из найденных), или end итератор, если объект не найден

\item count - возвращает количество объектов (ясно, что для map и set возвращает 0 или 1)

\item lower\_bound - возвращает итератор на место в последовательности, в которое можно вставить указанный элемент (если такой элемент уже есть,
вернется указатель на первый равный элемент)

\item upper\_bound - возвращает, аналогично, итератор на врехнюю границу (итератор на позицию перед большим элементом)

\item equel\_range - возвращает пару итераторов lower\_bound и upper\_bound
\end{itemize}

Следует еще раз обратить внимание на то, что c++ итераторы скорее указывают на промежутки между элементами.

\subsection{Требования к объектам}

\begin{itemize}
\item Для объектов хранимых в ассоциативных контейнеров требуется операция < (причем именно в строгой форме по семантике, иначе можно сломать дерево). Отсюда вопрос,
что делать с унаследованными классами, в которых нет оператора < или если мы хотим изменить семантику сравнения? Есть способ решить эти проблемы. На самом деле внутри
map и set используется некоторый класс:
\begin{lstlisting}
template<class T>
struct less {
	bool operator() (const T &a, const T &b) const {...}
}
\end{lstlisting}
и по-умолчанию, этот less использует оператор < для сравнения, т. к. класс шаблонный, его можно специализировать под свои нужды, и это есть первое решение проблемы.
Но если мы хотим иметь несколько различных способов сравнения, то на помощь приходят дополнительные параметры шаблона map, а именно, можно указать третьим параметром
наш собственный класс-функтор компаратор (аналогичный классу less).
\end{itemize}

\paragraph{Правильное удаление из map и set}

Исторически сложилось, что у метода erase нет возвращемого значения (хотя Microsoft так не считает), поэтому удаление из таких контейнеров выглядит примерно так:
\begin{lstlisting}
for (map<string, int>::iterator i = m.begin(); i != m.end();)
	if (i->first = "something")
		m.erase(it++);
	else
		++it;
\end{lstlisting}
обратите внимание на использование префиксной и постфиксной формы инкремента, так как постфиксная версия инкремента возвращает копию, а затем происходит переход
к следующему элементу и инвалидируется именно копия.